"""
# Worker Assignment
@ Eugene.Complexa.Ares
! MIT License
~ Assume that there are M factories and N workers, and distance Matrix D[M+N,M+N] (d[i][j] == 0 means no path), each m has degreeupperbound K.
Object: min(max(distance[n_i][m(n_i)]))
"""


import copy
import numpy as np


def read_data():
  first_line = input()
  first_line_split = first_line.split(' ')
  M, N, K = int(first_line_split[0]), int(first_line_split[1]), int(first_line_split[2])
  adjacent_matrix = [[0 for _ in range(M + N)] for __ in range(M + N)]
  row_num = M + N
  for row_idx in range(row_num):
    row = input()
    row_split = row.split()
    for column_idx, num in enumerate(row_split):
      adjacent_matrix[row_idx][column_idx] = int(num)
  #print(adjacent_matrix)
  remained_K = [K for _ in range(M)]  # 工厂剩余位置
  remained_workers = [id for id in range(N)]  # 剩余未分配的工人
  return M, N, remained_K, remained_workers, adjacent_matrix


def dijkstra(aj_matrix, s):
  distance = [float('inf') for _ in range(len(aj_matrix))]
  distance[s] = 0
  cost = []
  for i in range(len(aj_matrix)):
    cost.append([])
    for j in range(len(aj_matrix)):
      if aj_matrix[i][j] != 0:
        cost[i].append(aj_matrix[i][j])
      else:
        cost[i].append(float('inf'))
  used = [False for _ in range(len(aj_matrix))]
  while True:
    v = -1
    for u in range(len(aj_matrix)):
      if not used[u] and (v == -1 or distance[u] < distance[v]):
        v = u
    if v == -1:
      break

    used[v] = True
    for u in range(len(aj_matrix)):
      distance[u] = min(distance[u], distance[v] + cost[v][u])

  return distance


def get_workers_shortest_path_to_factory(M, N, aj_matrix):
  workers_index = [i for i in range(M, N + M)]  # 2 3 4 for the example
  workers_shortest_path_to_factory = [[float('inf') for _ in range(M)] for _ in range(N)]
  for i in range(N):
    distance = dijkstra(aj_matrix, workers_index[i])
    for j in range(M):
      workers_shortest_path_to_factory[i][j] = distance[j]
  return workers_shortest_path_to_factory


def compute_available_factories_helper(remained_K):
  """
  返回当前还未招满的工厂列表
  :param remained_K:
  :return:
  """
  available_factories_list = []
  for factory_idx, k in enumerate(remained_K):
    if k > 0:
      available_factories_list.append(factory_idx)
  return available_factories_list


def branch_and_bound_helper(current_selected_worker_node, remained_K, remained_workers,
              current_optimal_values, solutions,
              adjacent_matrix, workers_shortest_path_to_factory, ):
  """
  :param current_selected_worker_node: 当前选中的worker，并为其分配工厂
  :param remained_K: 剩余可选工厂（需要新建 object，不同分支后续不同）
  :param remained_workers: 剩余工人数量（需要新建 object，不同分支后续不同）
  :param current_optimal_values: 记录当前最优值（值拷贝不行，一定要用引用，因为后续定界要用到当前最优值，TODO: 所以一定要 global 共享，这里用一个list存储，该list只有一个元素）
  :param solutions: 当前完成分配的行走路径长度列表（需要新建 object，不同分支后续不同）
  :param adjacent_matrix: 邻接矩阵，不用变化（静态）
  :param workers_shortest_path_to_factory: 任意worker到任意factory的最短路径，不用变化（静态，TODO:注意可能有inf，i.e. 无穷大，无路径）
  :return:

  TODO 终止条件：
    TODO 剪支: 只要当前路径上任意一个距离 >= max_dis*
    TODO 无可行解: 当前worker 没有可选工厂（不用特殊处理，function会自动结束）
    TODO 有可行解并更新可行解: len(remained_workers) == 0
  """
  # 1: 为当前worker，遍历其所有可选的action（即工厂）
  for assignment_target in compute_available_factories_helper(remained_K):
    if workers_shortest_path_to_factory[current_selected_worker_node][assignment_target] != float('inf'):
      # 1) 当前工厂 assignment_target 可到达：
      distance = workers_shortest_path_to_factory[current_selected_worker_node][assignment_target]
      # TODO: 剪支，只要 > 当前最优解，就break
      if distance >= current_optimal_values[0]:
        break
      # 2) 更新solution路径列表
      new_solutions = solutions + [distance]
      # 3) 更新 remained_K (工厂assignment_target剩余位置-1)
      new_remained_K = copy.deepcopy(remained_K)
      new_remained_K[assignment_target] -= 1

      # 4) 选中下一个worker节点
      # TODO: 终止判断：判断是否还有剩余worker
      if len(remained_workers) == 0:
        # TODO: 找到一个可行解，跟当前最优解比较，进一步判断
        feasible_solution = np.max(solutions)
        if feasible_solution < current_optimal_values[0]:  # 小于当前最优解，则更新
          current_optimal_values[0] = feasible_solution
      else:
        new_selected_worker_node = remained_workers[0]
        new_remained_workers = remained_workers[1:]
        branch_and_bound_helper(new_selected_worker_node, new_remained_K, new_remained_workers,
                    current_optimal_values, new_solutions, adjacent_matrix,
                    workers_shortest_path_to_factory)


def solve(M, N, remained_K, remained_workers, adjacent_matrix):
  workers_shortest_path_to_factory = get_workers_shortest_path_to_factory(M, N, adjacent_matrix)
  #print(workers_shortest_path_to_factory)
  current_optimal_values = [float('inf')]
  solutions = []
  branch_and_bound_helper(current_selected_worker_node=remained_workers[0], remained_K=remained_K,
              remained_workers=remained_workers[1:], current_optimal_values=current_optimal_values,
              solutions=solutions, adjacent_matrix=adjacent_matrix,
              workers_shortest_path_to_factory=workers_shortest_path_to_factory)
  if current_optimal_values[0] == float("inf"):
    print(-1, "feasible solution")
  else:
    print(current_optimal_values[0])


if __name__ == "__main__":
  M, N, remained_K, remained_workers, adjacent_matrix = read_data()
  solve(M, N, remained_K, remained_workers, adjacent_matrix)